/*
 * UndoManager.java
 *
 * Created on October 29, 2006, 5:56 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package edu.umn.cs5115.scheduler.framework;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * The UndoManager is designed to allow for easy recording of undoable actions
 * as the program runs.  Whenever you make a change to data that should be 
 * undoable, register a class implementing the undoable interface to later undo
 * the changes.  You should also call "setActionName" to set the name of the
 * action (as it will appear in the undo menu) to something reasonable.<p>
 *
 * The UndoManager is designed so that somebody should call "beginUndoGrouping"
 * at the beginning of the event loop, and somebody should call 
 * "endUndoGrouping" at the end.  This allows all the changes that result from
 * a single bit of user interaction to be grouped together.<p>
 *
 * Much of this class's interface is inspired by NSUndoManager.
 * @author grant
 */
public class UndoManager extends KeyValueCodingBase
{
    /** Key that undo notifications are sent on. 
     * Undo notifications are sent whenever the item on top of the undo stack
     * changes.  This may indicate a change in action name, or a change in
     * undo availability. */
    public final static String UNDO_KEY = "undo";
    /** Key that redo notifications are sent on. 
     * Redo notifications are sent whenever the item on top of the redo stack
     * changes.  This may indicate a change in action name, or a change in redo
     * availability. */
    public final static String REDO_KEY = "redo";
    /** Items that have been done, and may need to be undone. */
    private LinkedList undoStack = new LinkedList();
    /** Items that have been undone, and may need to be redone. */
    private LinkedList redoStack = new LinkedList();
    /** The current UndoGroup stack.  May be empty if there is no group. */
    private LinkedList groupStack = new LinkedList();
    
    /** Are we undoing?  Used to prevent undo (or redo) from being invoked during an undo. */
    private boolean isUndoing = false;
    /** Are we redoing?  Used to prevent redo (or undo) from being invoked during a redo. */
    private boolean isRedoing = false;
    /** Number of times the UndoManager has been disabled and must be enabled. */
    private int undoDisabledCount = 0;
    
    /** Creates a new instance of UndoManager */
    public UndoManager()
    {
    }
    
    /**
     * Register an undoable for later undoing.  If the UndoManager is already
     * in the process of undoing something, this will instead register the 
     * action for redoing.  If the UndoManager is not in the process of undoing,
     * calling this method clears the redo stack.<p>
     * @param undoable An object to undo some action.  When undo or redo is 
     * invoked, this object's "undo" method will be called.  It should then
     * call methods to undo whatever was done while it was being created.
     */
    public void registerUndo(Undoable undoable)
    {
        if (undoDisabledCount <= 0)
        {
            boolean emptyStack = groupStack.isEmpty();
            if (!isUndoing && !isRedoing)
                redoStack.clear();
            if (emptyStack)
                beginUndoGrouping();
            // add to the current undo group.  If we're already undoing, this is
            // going to get pushed onto the undo stack.
            getInnermostUndoGroup().registerUndo(undoable);
            if (emptyStack)
                endUndoGrouping();
        }
    }

    /**
     * Get the action name for the current undo group, if there is an undo group
     * and the undo manager isn't undoing, or action name for the top most undo 
     * group on the undo stack stack otherwise.
     * @return The action name for this undo group.  (For example, if the 
     * menu should say "Undo Delete Class", this should return "Delete Class"
     * If there is no current group, and the stack is empty, or if the action
     * name was never set, this method returns the empty string ("").
     * @see #setActionName(String)
     * @see #getRedoActionName()
     */
    public String getUndoActionName()
    {
        UndoGroup theGroup = null;
        if (isUndoing)
        {
            if (!undoStack.isEmpty())
                theGroup = (UndoGroup) undoStack.getFirst();
        } else {
            UndoGroup undoGroup = getOutermostUndoGroup();
            if (undoGroup != null)
                theGroup = undoGroup;
            else if (!undoStack.isEmpty())
                theGroup = (UndoGroup) undoStack.getFirst();
        }
        if (theGroup != null)
            return theGroup.getActionName();
        else
            return "";
    }
    
    /**
     * Get the action name for the current redo group, if there is a redo group
     * and the undo manager is undoing, or action name for the top most redo 
     * group on the redo stack stack otherwise.
     * @return The action name for this redo group.  (For example, if the 
     * menu should say "Redo Delete Class", this should return "Delete Class"
     * If there is no current group, and the stack is empty, or if the action
     * name was never set, this method returns the empty string ("").
     */
    public String getRedoActionName()
    {
        UndoGroup theGroup = null;
        if (!isUndoing)
        {
            if (!redoStack.isEmpty())
                theGroup = (UndoGroup) redoStack.getFirst();
        } else {
            UndoGroup undoGroup = getOutermostUndoGroup();
            if (undoGroup != null)
                theGroup = undoGroup;
            else if (!redoStack.isEmpty())
                theGroup = (UndoGroup) undoStack.getFirst();
        }
        if (theGroup != null)
            return theGroup.getActionName();
        else
            return "";
    }

    /**
     * Sets the action name for the current undo group.  If there is no current
     * undo group, this instead sets the action name for the undo group on the
     * top of the undo stack.  If there is no current group and nothing on the
     * stack, calling this method does nothing.
     * @param actionName The new action name. This should be a string 
     * that will appear in the menu after the word "Undo" or "Redo". For
     * example, if the menu should say "Undo Delete Class", actionName 
     * should be "Delete Class"
     */
    public void setActionName(String actionName)
    {
        UndoGroup undoGroup = getOutermostUndoGroup();
        if (undoGroup == null)
        {
            if (!isUndoing)
            {
                if (!undoStack.isEmpty())
                    undoGroup = (UndoGroup) undoStack.getFirst();
            } else {
                if (!redoStack.isEmpty())
                    undoGroup = (UndoGroup) redoStack.getFirst();
            }
        }
            
        undoGroup.setActionName(actionName);
        if (!isUndoing)
            didChangeValueForKey(UNDO_KEY);
    }
    
    /** 
     * Marks the beginning of the undo group.  This starts recording all 
     * undoable actions in a group so that a single undo will invoke undo in
     * multiple undoables.  If called more than once, subsequent calls will 
     * continue to create new groups within the existing undo groups.
     * @see #endUndoGrouping()
     */
    public void beginUndoGrouping()
    {
        UndoGroup parentGroup = getInnermostUndoGroup();
        UndoGroup newGroup = new UndoGroup();
        if (parentGroup != null)
            parentGroup.registerUndo(newGroup);
        else {
            if (!isUndoing && !isRedoing)
                didChangeValueForKey(UNDO_KEY);
        }
        groupStack.addFirst(newGroup);
    }
    
    /** 
     * Marks the end of an undo group.  The current undo group is closed, and
     * if non-empty, added to the next group down.  If there is not another 
     * group to enclose this one, it is pushed onto the undo stack (or redo 
     * stack as appropriate).  If there is no current undo group, calling this
     * method has no effect.
     * @see #beginUndoGrouping()
     */
    public void endUndoGrouping()
    {
        UndoGroup undoGroup = getInnermostUndoGroup();
        if (undoGroup != null)
        {
            groupStack.removeFirst();
            if (undoGroup.isValid())
            {
                if (getInnermostUndoGroup() == null)
                {
                    if (isUndoing)
                        redoStack.addFirst(undoGroup);
                    else
                        undoStack.addFirst(undoGroup);
                }
            }
        }
    }
    
    /**
     * Check the depth of undo groups.
     * @return The depth of nested undo groupings.
     */
    public int getUndoGroupLevel()
    {
        return groupStack.size();
    }
    
    /**
     * Tests whether undo is available. This means that there is something that 
     * can be undone and the UndoManager is not already in the process of 
     * undoing or redoing something.
     * @return True if undo is available, and something will be undone if undo()
     * is called, false otherwise.
     */
    public boolean canUndo()
    {
        UndoGroup undoGroup = getOutermostUndoGroup();
        return (!undoStack.isEmpty() || (undoGroup != null && !undoGroup.isEmpty())) && 
                !(isUndoing || isRedoing);
    }
    
    /**
     * Tests whether redo is available. This means that there is something that 
     * can be redone and the UndoManager is not already in the process of 
     * undoing or redoing something.
     * @return True if redo is available, and something will be redone if redo()
     * is called, false otherwise.
     */
    public boolean canRedo()
    {
        return !redoStack.isEmpty() && !(isUndoing || isRedoing);
    }
    
    /**
     * Undoes the group or item on the top of the undo stack.  If an undo group
     * is currently open, calling this method will close it first. As undo is 
     * running, undoables that are registered will be pushed onto the redo stack
     * as a single item.
     */
    public void undo()
    {
        if (canUndo())
        {
            while (!groupStack.isEmpty())
                endUndoGrouping();
            UndoGroup topGroup = (UndoGroup) undoStack.removeFirst();
            isUndoing = true;
            beginUndoGrouping();
            topGroup.undo();
            setActionName(topGroup.getActionName());
            endUndoGrouping();
            isUndoing = false;
            validateUndoItems();
            didChangeValueForKey(UNDO_KEY);
            didChangeValueForKey(REDO_KEY);
        }
    }
    
    /**
     * Redoes the group on the top of the redo stack.  As redo is running,
     * undoables that are registered will be pushed back onto the undo stack as
     * a single item.
     */
    public void redo()
    {
        if (canRedo())
        {
            while (!groupStack.isEmpty())
                endUndoGrouping();
            UndoGroup topGroup = (UndoGroup) redoStack.removeFirst();
            isRedoing = true;
            beginUndoGrouping();
            topGroup.undo();
            setActionName(topGroup.getActionName());
            endUndoGrouping();
            isRedoing = false;
            validateUndoItems();
            didChangeValueForKey(UNDO_KEY);
            didChangeValueForKey(REDO_KEY);
        }
    }
    
    /**
     * Disables undo registration.  After calling this, calls to registerUndo
     * will be ignored.  To re-enable undo, you must call enableUndoRegistration
     * once for each time you call disableUndoRegistration.
     * @see #enableUndoRegistration()
     */
    public void disableUndoRegistration()
    {
        undoDisabledCount++;
    }
    
    /**
     * Enables undo registration.  Undo is enabled by default, so you should 
     * only call this to balance prior calls to disableUndoRegistration.
     * @throws IllegalStateException If you attempt to enableUndoRegistration 
     * while it is not disabled.
     * @see #disableUndoRegistration()
     */
    public void enableUndoRegistration()
    {
        if (undoDisabledCount > 0)
            undoDisabledCount--;
        else
            throw new IllegalStateException("Enabled undo when undo was not disabled.");
    }
    
    /**
     * Test if undo is currently in progress.
     * @return True if undo is running, false otherwise.
     */
    public boolean isUndoing()
    {
        return isUndoing;
    }

    /**
     * Test if redo is currently in progress.
     * @return True if redo is running, false otherwise.
     */
    public boolean isRedoing()
    {
        return isRedoing;
    }
    
    /**
     * Get the current state of the undo stack.  This is an integer which you 
     * can compare to future return values.  If it is the same, then the undo
     * stack is in the same state as it was in the first call, which is to say
     * there are no more undoable changes that have not been undone.  This is
     * useful for finding out if changes have been made since a certain point
     * in history (which is useful for checking for unsaved changes.)
     */
    public int getUndoStackState()
    {
        if (undoStack.isEmpty())
            return 0;
        else
            return (((UndoGroup)undoStack.getFirst()).getID());
    }

    /**
     * Returns the innermost undo group on the undo group stack.
     * @return The group on the top of the undo group stack, or null if the 
     * stack is empty.
     */
    private UndoGroup getInnermostUndoGroup()
    {
        if (groupStack.isEmpty())
            return null;
        else
            return (UndoGroup) groupStack.getFirst();
    }
    
    /**
     * Returns the outermost undo group on the undo group stack.
     * @return The group on the bottom of the undo group stack, or null if the
     * stack is empty
     */
    private UndoGroup getOutermostUndoGroup()
    {
        if (groupStack.isEmpty())
            return null;
        else
            return (UndoGroup) groupStack.getLast();
    }

    /**
     * Checks that the tops of the stacks are valid.  Removes invalid items, if
     * any.
     */
    public void validateUndoItems()
    {
        if (validateStack(undoStack))
            didChangeValueForKey(UNDO_KEY);
        if (validateStack(redoStack))
            didChangeValueForKey(REDO_KEY);
    }
    
    /**
     * Validate at stack by calling isValid on the top item and repeatedly 
     * removing the top item until the stack is empty or an item returns true.
     * @return True if any items were removed from the stack due to validation,
     * false otherwise.
     */
    private boolean validateStack(LinkedList stack)
    {
        boolean modified = false;
        while(!stack.isEmpty() && !((Undoable)stack.getFirst()).isValid())
        {
            stack.removeFirst();
            modified = true;
        }
        return modified;
    }
    
    /**
     * We don't define methods getUndo() or getRedo(), since they don't make 
     * sense, but notify on those keys anyway.  This intercepts requests for
     * the undo and redo keys and silently ignores them.
     * (KeyValueCodingBase will request these keys to determine their type after
     * we claim to have changed them to know if it should set up set listener 
     * forwarding)
     */
    protected Object getValueForUndefinedKey(String key)
    {
        if (key == UNDO_KEY || key == REDO_KEY)
            return null;
        return super.getValueForUndefinedKey(key);
    }
    
    /**
     * Groups undoable actions together, so that they can be undone at once.
     * Calling undo on an undo group causes it to call undo on all its 
     * undoables.
     */
    private static class UndoGroup extends Undoable
    {
        /** 
         * ID numbers are used to figure out if the undo stack is such that it
         * is identical to a state it was in earlier.  Hence, each undo group
         * needs a unique identifier, which is assigned when it is created.
         */
        private static int nextID = 1;
        /** Items to undo. */
        private LinkedList groupItems = new LinkedList();
        /** Name of the action that this group represents for display in a menu. */
        private String actionName;
        /** UndoGroup serial number */
        private int ID;
        
        // this is initialization code that always runs when instances of this
        // class are constructed.
        {
            // Assign the unique ID.
            ID = nextID;
            nextID++;
        }
        
        /**
         * Undo all of the items in the undo group.
         */
        public void undo()
        {
            Iterator iterator = groupItems.iterator();
            while(iterator.hasNext())
            {
                Undoable undoable = (Undoable) iterator.next();
                undoable.undo();
            }
        }
        
        /**
         * Add an undoable to this group.  It's "undo" method will be called 
         * when undo is called on the entire group.
         * @param undoable The undoable object to add to this group.
         * @see Undoable#undo()
         */
        public void registerUndo(Undoable undoable)
        {
            groupItems.addFirst(undoable);
        }
        
        /**
         * Returns whether or not there is really something in this undo group.
         * @return True if the group contains nothing or only other empty 
         * groups, false if there's an undoable that's not an UndoGroup in the
         * group.
         */
        public boolean isEmpty()
        {
            boolean empty = true;
            Iterator iterator = groupItems.iterator();
            
            // scan through all items in the group
            while(iterator.hasNext() && empty)
            {
                Object undoable = iterator.hasNext();
                
                // if this is an UndoGroup, check to see if it's empty
                if (undoable instanceof UndoGroup)
                {
                    if (!((UndoGroup)undoable).isEmpty())
                        empty = false;
                } else // otherwise, we're not empty
                    empty = false;
            }
            return empty;
        }

        /**
         * Checks the validity of this group.
         * @return True if the group contains something that is valid, false
         * if only invalid items (or no items at all) are in the group.
         */
        public boolean isValid()
        {
            boolean valid = false;
            Iterator iterator = groupItems.iterator();
            
            while(iterator.hasNext())
            {
                Undoable undoable = (Undoable) iterator.next();
                if (!undoable.isValid())
                    iterator.remove();
                else
                    valid = true;
            }
            return valid;
        }
        
        /**
         * Get the action name for this undo group.  (For example, if the menu
         * should say "Undo Delete Class", this should return "Delete Class"
         * @return The action name for this undo group.
         * @see #setActionName
         */
        public String getActionName()
        {
            if (actionName != null)
                return actionName;
            else
                return "";
        }

        /**
         * Sets the action name for this undo group.
         * @param actionName The new action name. This should be a string 
         * that will appear in the menu after the word "Undo" or "Redo". For
         * example, if the menu should say "Undo Delete Class", actionName 
         * should be "Delete Class"
         */
        public void setActionName(String actionName)
        {
            this.actionName = actionName;
        }

        /**
         * Get an integer that uniquely identifies this undo group.
         * @return This UndoGroup's serial number.
         */
        public int getID()
        {
            return ID;
        }
    }
}
